#include <iostream>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
using namespace std;

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        vector<string> ret;
        // 统计字符串出现次数：用map自动按字符串升序存储，方便后续相同次数时保持字典序
        map<string, int> m_count;
        for (auto& str : words) 
        {
            m_count[str]++;
        }

        // 使用multimap排序：
        // 1. 不用map是因为map的key（次数）可能重复，而multimap允许key重复
        // 2. 不用sort+vector的方式是此处选择更直接的容器特性实现（非sort不能实现，只是实现方式不同）
        // 3. 通过使用仿函数用greater<int>指定排序规则，使multimap按次数降序排列（默认是less<int>升序）
        multimap<int, string, greater<int>> mul_count;
        for (auto& e : m_count) 
        {
            // 从map插入时，相同次数的字符串已按字典序升序排列（因map本身按字符串升序），故multimap中相同次数的字符串顺序正确
            mul_count.insert(make_pair(e.second, e.first));
        }

        // 取出前k个：正向遍历multimap，确保次数降序，相同次数时字符串升序
        multimap<int, string>::iterator it = mul_count.begin();
        while (it != mul_count.end() && k > 0) 
        {
            ret.push_back(it->second);
            k--;
            it++;
        }
        return ret;
    }
};